package de.hsb.ai.agent.misterx.minimax;

import jade.core.AID;

import java.util.Iterator;
import java.util.List;
import java.util.Set;

import org.apache.commons.collections.MultiMap;

/**
 * Alpha-Beat Alghoritmus
 * @author Dennis
 *
 */
public class AlphaBeta implements ISearchStrategy {
	
protected static final int MAX_ROUND = 0;
protected static final int MIN_ROUND = 1;
protected static final int MAX_DEPTH = 3;


private ITerminalTest _terminalTest;

	/**
	 * Konstruktor
	 * @param terminalTest Terminal-Test Objekt
	 */
	public AlphaBeta(ITerminalTest terminalTest) {
		this._terminalTest = terminalTest;
	}

	/**
	 * Hier wird die Minimax-Suche gestartet
	 * @param node = Ausgangsstatus für die Suche
	 */
	public int SEARCH(Node node) {
		this._terminalTest.update();
		
		//Bottom-Up Kosten Ermittlung
		int bestValue = MAX_VALUE(node, Integer.MIN_VALUE, Integer.MAX_VALUE);
		
		return AlphaBetaHelper.getSuccessorWithBestValue(node, bestValue);

	}
	
	/**
	 * MAX-Suche
	 * @param node Node für den die MAX-Suche durchgeführt werden soll
	 * @param alpha Alpha-Wert der Max-Suche
	 * @param beta Beta-Wert der Max-Suche
	 * @return bester Wert der in der Max-Suche ermittelt wurde
	 */
	private int MAX_VALUE(Node node, int alpha, int beta) {
		
		if(this._terminalTest.TERMINAL_TEST(node, MAX_ROUND)) return node._cost;
			
		int value = alpha;

		List<Integer> options = AlphaBetaHelper.getMoveOptions(node._mrXState);
		for(int i = 0; i < options.size(); i++) {
			Node child = new Node(node, options.get(i), node._depth+1);
			node._childs.add(child);
			value = Math.max(MIN_VALUE(child, alpha, beta), value);
			if(value >= beta){
				node._cost = value;
				return value; //Abbruch der Untersuchung (prunning)
			}
			alpha = Math.max(alpha, value);
		}
		
		//Kosten eintragen für den childNode.
		node._cost = value;
		
		return value;
	}
	
	/**
	 * MIN-Suche
	 * @param node Node für den die MIN-Suche durchgeführt werden soll
	 * @param alpha Alpha-Wert der MIN-Suche
	 * @param beta Beta-Wert der MIN-Suche
	 * @return bester Wert der in der MIN-Suche ermittelt wurde
	 */
	@SuppressWarnings("unchecked")
	private int MIN_VALUE(Node node, int alpha, int beta) {
		

		if(this._terminalTest.TERMINAL_TEST(node, MIN_ROUND)) return node._cost;
			
		int value = beta;
		
		MultiMap options = AlphaBetaHelper.getDetectiveMoveOptions(node._detectiveStates);
		Set<Integer> keySet = options.keySet();
	    Iterator<Integer> iter = keySet.iterator();
	    while (iter.hasNext() ) {
	        int key = (int) iter.next();
	        List<AID> values = (List<AID>) options.get( key );
			Node child = new Node(node, key, node._depth+1, values);
			node._childs.add(child);
			value = Math.min(MAX_VALUE(child, alpha, beta), value);
			if(value <= alpha){
				node._cost = value;
				return value; //Abbruch der Untersuchung (prunning)
			}
			
			beta = Math.min(beta, value);
	    }
	    
		/*
		for(int i = 0; i < options.size(); i++) {
			System.out.println("Nodes: " + count++);
			Node child = new Node(node, options.get(i), node._depth+1, detective);
			node._childs.add(child);
			value = Math.min(MAX_VALUE(child, alpha, beta), value);
			if(value <= alpha) return value; //Abbruch der Untersuchung (prunning)
			
			beta = Math.min(beta, value);
		}
		*/
		
	    node._cost = value;
		
		return value;

	}
}
